
//
//  BST_remove.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/20.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension BinarySearchTree {
    
    func remove(at node: Node<Element>, hot: inout Node<Element>?) {
        var nd = node
        // 实际被删除节点的接替者
        var succ: Node<Element>?
        if !nd.hasLchild {
            succ = nd.rchild
        } else if !nd.hasRchild {
            succ = nd.lchild
        } else {
            // 右子树存在  所以不会为nil
            nd = node.inOrderSuccessor!
            // 交换这两个位置的值 不会影响BST有序性
            // 因为中序的BST就是有序的 取其直接后继不影响其有序性
            swap(&nd.value, &node.value)
            // 原问题就转换为删除一个只有右子树的节点的为题
            succ = nd.rchild
        }
        // 记录实际被删除节点的父亲
        hot = nd.parent
        // 将被删除节点的接替者与hot相连
        succ?.parent = hot
        if hot == nil {
            _root = succ // 保证根节点不出错
        }
        // 将hot与被删除节点的接替者相连
        let isLchild = nd.isLchild
        isLchild ? (hot?.lchild = succ) : (hot?.rchild = succ)
    }
}
